package course;

import java.util.*;
import java.util.LinkedList;

import linkedList.TreeNode;

/**
 * 最大二叉搜索子树问题的对数器工具类
 * 支持一键验证你的解法是否正确
 */
public class LargestBSTValidator {

    // ====================== 官方正确解法（作为标准答案）======================
    public static int[] largestBSTUtil(TreeNode root) {
        if (root == null) {
            return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        }

        if (root.left == null && root.right == null) {
            return new int[]{root.val, root.val, 1};
        }

        int[] left = largestBSTUtil(root.left);
        int[] right = largestBSTUtil(root.right);

        int[] ans = new int[3];

        if (left[1] < root.val && root.val < right[0]) {
            ans[0] = Math.min(left[0], root.val);
            ans[1] = Math.max(right[1], root.val);
            ans[2] = left[2] + right[2] + 1;
            return ans;
        }

        ans[0] = Integer.MIN_VALUE;
        ans[1] = Integer.MAX_VALUE;
        ans[2] = Math.max(left[2], right[2]);
        return ans;
    }

    public static int officialLargestBst(TreeNode root) {
        return largestBSTUtil(root)[2];
    }

    // ====================== 随机生成测试用的二叉树 ======================
    private static Random random = new Random();

    public static TreeNode generateRandomTree(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    private static TreeNode generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || random.nextDouble() < 0.3) {
            return null;
        }
        TreeNode node = new TreeNode(random.nextInt(maxValue) - random.nextInt(maxValue));
        node.left = generate(level + 1, maxLevel, maxValue);
        node.right = generate(level + 1, maxLevel, maxValue);
        return node;
    }

    // ====================== 深拷贝树（避免被算法修改）======================
    public static TreeNode copyTree(TreeNode root) {
        if (root == null) return null;
        TreeNode copy = new TreeNode(root.val);
        copy.left = copyTree(root.left);
        copy.right = copyTree(root.right);
        return copy;
    }

    // ====================== 验证你的方法 ======================
    @FunctionalInterface
    public interface SolutionMethod {
        int apply(TreeNode root);
    }

    /**
     * 一键验证你的解法是否正确
     * @param yourMethod 你的解法（函数式接口）
     */
    public static void verify(SolutionMethod yourMethod) {
        int testTimes = 1000;
        int maxLevel = 7;
        int maxValue = 100;
        boolean pass = true;

        System.out.println("开始验证... 共测试 " + testTimes + " 次");

        for (int i = 0; i < testTimes; i++) {
            TreeNode root = generateRandomTree(maxLevel, maxValue);
            TreeNode copy1 = copyTree(root);
            TreeNode copy2 = copyTree(root);

            int expected = officialLargestBst(copy1);
            int actual = yourMethod.apply(copy2);

            if (expected != actual) {
                System.out.println("❌ 测试失败！第 " + (i + 1) + " 次");
                System.out.println("期望: " + expected + ", 实际: " + actual);
                printTree(root);
                pass = false;
                break;
            }
        }

        if (pass) {
            System.out.println("✅ 所有测试通过！");
        }
    }

    // ====================== 辅助：打印树结构（可选）======================
    public static void printTree(TreeNode root) {
        System.out.println("Tree structure (level-order):");
        if (root == null) {
            System.out.println("null");
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                System.out.print(node.val + " ");
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                System.out.print("null ");
            }
        }
        System.out.println();
    }
}